package dp.pack.backtrack;

/**
 * 01背包回溯法暴力解决
 */
public class Knapsack {

    // 记录最大价值
    private static int maxProfit = Integer.MIN_VALUE;

    public static void main(String[] args) {
        // 背包的容量
        int capacity = 10;
        // 物品的重量
        int[] weights = {2, 3, 4, 5};
        // 物品对应的价值
        int[] values = {3, 4, 5, 6};
        backtrack(weights, values, 0, capacity, 0);
        System.out.println("最大价值是："+ maxProfit);
    }

    /**
     *
     * @param weight 物品重量
     * @param value 物品价值
     * @param startIndex 遍历开始索引
     * @param reCapacity 剩余容量
     * @param currProfit 当前价值
     */
    private static void backtrack(int weight[],int value[],int startIndex,int reCapacity,int currProfit) {
        // 到达叶子节点
        if (startIndex == weight.length) {
            maxProfit = Math.max(maxProfit,currProfit);
            return;
        }

        for (int i = startIndex; i < weight.length; i++) {
            // 装当前物品
            if (reCapacity >= weight[i]) {
                backtrack(weight,value,i+1,reCapacity-weight[i],currProfit+value[i]);
            } else {
                backtrack(weight,value,i+1,reCapacity,currProfit);
            }
        }
    }
}
